package alo.p11.work;

/**
 * @ClassName MaxIndex
 * @Description 查找最大的j-i使得A[j]>A[i]
 * @Author Fanxc
 * @DATE 2021/3/14 10:13
 * @Version 1.0
 */
public class MaxIndex {
    int maxIndex(int[] A,int n){
        int maxDiff;
        int i,j;
        int[] leftMin=new int[n];
        int[] rightMax=new int[n];
        leftMin[0]=A[0];
        for (i=1;i<n;i++){
            leftMin[i]=Math.min(A[i],leftMin[i-1]);
        }
        rightMax[n-1]=A[n-1];
        for (j=n-1;j>=0;j--){
            rightMax[j]=Math.max(A[j],rightMax[j+1]);
        }
        i=0;j=0;maxDiff=-1;
        while (j<n&&i<n){
            if (leftMin[i]<rightMax[j]){
                maxDiff=Math.max(maxDiff,j-i);
                j=j+1;
            }else {
                i=i+1;
            }
        }
        return maxDiff;
    }
}
